/*
* leetcode 取金币
*
链接：https://ac.nowcoder.com/acm/problem/221822
给定一个长度为 n 的正整数数组 coins，每个元素表示对应位置的金币数量。
取位置 i 的金币时，假设左边一堆金币数量是L，右边一堆金币数量为R，
则获得L∗cost[i]∗R的积分。如果左边或右边没有金币，则金币数量视为1。
请你计算最多能得到多少积分。

数据范围：数组长度满足1≤n≤100  ，数组中的元素满足 1≤coins≤100
示例1
[5,6,4,8]
480
说明：
第一步取 4，得 6*4*8 = 192，余下 5 6 8。
第二步取 6，得 5*6*8 = 240，余下 5 8。
第三步取 5，得 5*8*1 = 40，余下 8。
最后取 8，得 1*8*1 = 8 。
最终积分为 192+240+40+8 = 480。
* */
/*
* */
import java.util.*;
public class Solution {
    public int getCoins (ArrayList<Integer> coins) {
        int n=coins.size();
        int[] arr=new int[n+2];
        arr[0]=arr[n+1]=1;
        for(int i=1;i<=n;i++)arr[i]=coins.get(i-1);
        int[][] dp=new int[n+2][n+2];
        for(int i=n;i>0;i--){
            for(int j=i;j<=n;j++){
                for(int k=i;k<=j;k++){
                    dp[i][j]=Math.max(dp[i][j],dp[i][k-1]+dp[k+1][j]+arr[i-1]*arr[k]*arr[j+1]);
                }
            }
        }
        return dp[1][n];
    }
}